//package java8;
//
//import lombok.AllArgsConstructor;
//
//import java.util.*;
//
//public class BSTPrintUtils {
//    public static void printBST(TreeNode root, int keyLength) {
//        if (root == null) {
//            return;
//        }
//        int maxLength = levelLength(6, 3);
//
//        List<List<Object>> draws = new ArrayList<>();
//        Queue<Wrapper> q = new LinkedList<>();
//        Queue<Wrapper> q2 = new LinkedList<>();
//        q.add(new Wrapper(false, root, null, (maxLength - root.string().length()) / 2, null));
//
//        Wrapper tmp = null;
//        while ((tmp = q.poll()) != null || !q2.isEmpty()) {
//            if (tmp == null) {
//                ((LinkedList<Wrapper>) q).addAll(q2);
//                q2.clear();
//                continue;
//            }
//            if (!tmp.line) {
//                draws.add(Arrays.asList(true, tmp.offset, tmp.data.string()));
//                if (tmp.data.getLeft() != null) {
//                    //draws.add(new Tuple(false, tmp.offset - 1, "/"));
//                    q.add(new Wrapper(true, null, null, tmp.offset - 1, "/"));
//                    q2.add(new Wrapper(false, tmp.data.getLeft(), tmp.data, tmp.offset - 1 - keyLength / 2, null));
//                }
//                if (tmp.data.getRight() != null) {
//                    //draws.add(new Tuple(false, tmp.offset + tmp.data.string().length(), "\\"));
//                    q.add(new Wrapper(true, null, null, tmp.offset + keyLength, "\\"));
//                    q2.add(new Wrapper(false, tmp.data.getRight(), tmp.data, tmp.offset + keyLength + keyLength / 2, null));
//                }
//
//            } else {
//                draws.add(Arrays.asList(false, tmp.offset, tmp.lineContent));
//            }
//        }
//
//        boolean newLine = true;
//        boolean first = true;
//        for (int i = 0; i < draws.size(); i++) {
//            List<Object> draw = draws.get(i);
//            if ((boolean) draw.get(0) != newLine) {
//                System.out.println();
//                newLine = !newLine;
//                first = true;
//            }
//
//            if (first) {
//                for (int j = 0; j < (int) draw.get(1); j++) {
//                    System.out.print(" ");
//                }
//                first = false;
//            } else {
//                for (int j = 0; j < (int) draw.get(1) - (int) draws.get(i - 1).get(1); j++) {
//                    System.out.print(" ");
//                }
//            }
//            System.out.print((String) draw.get(2));
//        }
//
//    }
//
//
//    private static int levelLength(int level, int keyLength) {
//        return (int) Math.pow(2, level);
//    }
//
//    @AllArgsConstructor
//    private static class Wrapper {
//        public boolean line;
//        public TreeNode data;
//        public TreeNode parent;
//        public int offset;
//        public String lineContent;
//    }
//
//
//    public static void main(String[] args) {
//        BST<Integer, String> bst = new BST<>();
//        bst.insert(10, "a");
//        bst.insert(15, "b");
//        bst.insert(13, "b");
//        bst.insert(12, "b");
//        bst.insert(3, "d");
//        bst.insert(5, "cdd");
//        bst.insert(33, "cff");
//        bst.insert(38, "ceee");
//        bst.insert(1, "aaaa");
//        bst.insert(0, "dddd");
//        bst.insert(99, "dddd");
//        bst.insert(100, "dddd");
//        bst.insert(7, "dddd");
//        bst.insert(1, "dddd");
//        //从根开始打印
//        BSTPrintUtils.printBST(bst.getRoot(), 2);
//
//    }
//
//
//    static class Node<K extends Comparable<K>, V> implements TreeNode {
//        K k;
//        V v;
//        Node left, right;
//
//        public Node(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//
//
//        @Override
//        public String string() {
//
//            return String.valueOf(k);
//        }
//
//        @Override
//        public TreeNode getLeft() {
//            // TODO Auto-generated method stub
//            return left;
//        }
//
//        @Override
//        public TreeNode getRight() {
//            // TODO Auto-generated method stub
//            return right;
//        }
//
//    }
//
//}
//
//class BST<K extends Comparable<K>, V> {
//    private int count;
//    private BSTPrintUtils.Node<K, V> root;
//    private int maxLevel;
//
//    public int size() {
//        return count;
//    }
//
//    public boolean isEmpty() {
//        return count == 0;
//    }
//
//    public void insert(K k, V v) {
//        BSTPrintUtils.Node<K, V> node = new BSTPrintUtils.Node<>(k, v);
//        if (insertToNode(root, node, 0)) {
//            // 如果是插入则将count+1
//            count++;
//        }
//    }
//
//    public BSTPrintUtils.Node getRoot() {
//        return root;
//    }
//
//    /**
//     * @param parint
//     * @param node
//     * @return 如果新增返回true，如果只是更新返回false
//     */
//    private boolean insertToNode(BSTPrintUtils.Node<K, V> parent, BSTPrintUtils.Node<K, V> node, int level) {
//        if (root == null) {
//            root = node;
//            maxLevel = 1;
//            return true;
//        }
//        if (parent.k.compareTo(node.k) == 0) {
//            // key相同则更新
//            parent.v = node.v;
//            return false;
//        } else if (parent.k.compareTo(node.k) < 0) {
//            // 如果node比parent大，则插入到右子树
//            if (parent.right == null) {
//                parent.right = node;
//                if (level + 1 > maxLevel) {
//                    maxLevel = level + 1;
//                }
//                return true;
//            }
//            return insertToNode(parent.right, node, level + 1);
//        } else {
//            // 如果node比parent小，则插入左字数
//            if (parent.left == null) {
//                parent.left = node;
//                if (level + 1 > maxLevel) {
//                    maxLevel = level + 1;
//                }
//                return true;
//            }
//            return insertToNode(parent.left, node, level + 1);
//        }
//
//    }
//
//
//}
//
//
